Opinon by Judge THOMAS; Opinion concurring in part and dissenting in part by Judge TASHIMA.

OPINION

In this appeal we consider, inter alia, whether the district court properly granted summary judgment on John D. Hensa-la’s claims that the United States Air Force’s educational recoupment policy violated his constitutional rights. We conclude that genuine issues of fact preclude summary judgment as to some of the claims, and remand the case to the district court for further proceedings.

I

Since 1957, the Uniform Code of Military Justice has criminalized sex between service members of the same gender and provided that such conduct is an offense punishable by court martial. 10 U.S.C. § 925 . In 1993, Congress enacted the so-called “Don’t Ask, Don’t Tell” policy, codified at 10 U.S.C. § 654 (b), which limits the basis under which a service member will be ordered separated from the armed services for violations of § 925. In particular, *953 the “Don’t Ask, Don’t Tell” policy (1) enumerated five exceptions under which evidence of a § 925 violation will not lead to discharge, see § 654(b)(1); and (2) provided that if a service member “has stated that he or she is a homosexual or bisexual, or words to that effect,” a presumption arises that the member violated § 925, but the presumption can be rebutted by evidence of celibacy. See 10 U.S.C. § 654 (b)(2).

This general policy has been incorporated into the administration of the Armed Forces Health Professional Scholarship Program (“the Scholarship Program”), a national program that provides an individual with financial assistance for expenses arising from his medical education in exchange for an enforceable commitment to serve on active duty as a physician for a specified period of time. Pursuant to 10 U.S.C. § 2005 , the Secretaries of each branch of the military may require a scholarship contract to provide “that if such person, voluntarily or because of misconduct, fails to complete the period of active duty specified in the agreement ... such person will reimburse the United States” proportionately to the unserved duty. 10 U.S.C. § 2005 .

On May 17, 1994, Deputy Secretary of Defense John M. Deutch issued a memorandum (“the Deutch Memo”) interpreting 10 U.S.C. § 2005 in light of the “Don’t Ask, Don’t Tell” policy. As relevant here, the Deutch Memo provided that although a service member’s statement of sexual orientation, sometimes referred to as a “coming out statement,” when not offset by evidence of celibacy, is sufficient for grounds of separation from the armed forces, such a statement is insufficient to constitute a basis for recoupment. The Deutch Memo indicated that recoupment would be appropriate “where, based on the circumstances, it is determined that the member made the statement for the purpose of seeking separation.” The parties concede that, for the purposes of the instant case, the Deutch Memo reflects the operative recoupment policy of the United States Air Force.

Hensala is a physician and former Air Force Reserve captain. Prior to his entry into medical school, Hensala applied for and became a recipient of the Scholarship Program. After executing a contract implementing the terms of the Scholarship Program, Hensala began pursuing his medical education at Northwestern University Medical School.

The contract at issue contained a provision that Hensala would reimburse any money expended on his behalf in the event that he fails to complete the period of active duty due to voluntary separation for any reason or involuntary separation for specified reasons. In particular, the contract provided that:

In 1990, Hensala graduated from Northwestern University Medical School, and pursuant to the terms of the contract, was appointed Captain of the Air Force Reserve, Medical Corps. Hensala requested and received two deferments of active duty for the purpose of completing a three-year psychiatric residency and a two-year fellowship in child psychiatry.

In 1994, the Air Force notified Hensala that his active duty would commence in *954 1995 and requested the completion of a physical examination, a prerequisite to his appointment to active duty. On December 12, 1994, Hensala sent a letter to Colonel Daniel Degracias of the Air Force Directorate of Medical Service Officer Management informing the Colonel that “I am gay” and that “I do not believe this will affect my ability to serve in the Air Force as a child psychiatrist....” The Air Force did not send a direct response to Hensala at this time.

Hensala completed his physical examination in January 1995. In April, he was ordered to commence active duty at Scott Air Force Base, located in Kansas, on June 26,1995.

In approximately April or May 1995," Hensala called his supervisor and commanding officer, Lieutenant Colonel Jay Weiss, and informed him that he was gay and intended to live with his partner when stationed at Scott Air Force Base. According to Hensala, Lt. Colonel Weiss responded that such an arrangement was acceptable as long as Hensala neither brought his partner to the housing office nor publicized their relationship.

Also in the spring of 1995, Major Albert Klein contacted Hensala and informed him that he had been appointed to serve as Hensala’s counsel in the investigation of Hensala’s statements regarding his sexual orientation. Major Klein allegedly advised Hensala to provide a list of references who could confirm his sexual orientation. Hensala complied by providing a list of organizations and individuals. Major Klein forwarded this list to Colonel Rockne Buraglio, a reserve judge advocate. In June 1995, the Air Force suspended Hensala’s orders to report to active duty.

In August 1995, the Air Force appointed Colonel Buraglio as the investigating officer over the matter. Colonel Buraglio conducted a recorded interview with Hen-sala who was represented by counsel. At this interview, Hensala explained that in 1988, he realized he was gay, and at that time, he informed only a small number of close friends of his sexual orientation. Over time, he became more comfortable with his sexual orientation, and in 1994, he realized he could no longer conceal his sexual orientation from co-workers and supervisors. Hensala contended he was motivated to inform the Air Force of his sexual orientation because of his growing comfort with it and his increased discomfort with keeping his orientation a secret.

Hensala also asserted that at the time he contacted Colonel Degracias, he was not aware of the recoupment policy, and that his attorney and media were the sources of his understanding of the armed forces’ “Don’t Ask, Don’t Tell” policy. At the close of the interview, Hensala reaffirmed his desire to serve on active duty.

In January 1997, Colonel Buraglio sent a letter to the Air Reserve Personnel Center reporting his findings from the investigation, which included a conclusion that Hen-sala informed the Air Force of his sexual orientation for the purpose of avoiding active duty. Colonel Buraglio thus recommended that the Air Force discharge Hen-sala and seek recoupment pursuant to the operative regulations.

In February 1997, the Air Force informed Hensala of its intention to discharge him and seek recoupment because he had “made a personal statement regarding a propensity for homosexual conduct for the purpose of obtaining separation.” On May 15,1997, Hensala informed the Air Force of his decision not to tender his resignation and waived an opportunity to contest the Air Force’s recommendation for discharge at an administrative proceeding on the basis that such a hearing would be futile.

*955 On June 30,1997, the Air Force Reserve Personnel Center forwarded the Hensala case to the Air Force Personnel Council with a recommendation of discharge and recoupment. On October 21, 1997, the Personnel Council voted unanimously to follow such recommendation. On November 5,1997, the Secretary of the Air Force discharged Hensala pursuant to 10 U.S.C. § 654 and ordered recoupment in the amount of $71,429.53 pursuant to 10 U.S.C. § 2005 .

On August 14, 1998, Hensala petitioned the Air Force Board for Correction of Military Records (“Corrections Board”) to rescind the recoupment order, but did not challenge the underlying discharge. On April 11, 2000, the Corrections Board issued a written opinion denying the petition.

Hensala filed an action with the district court, alleging that the recoupment order violated (1) the Administrative Procedure Act, 5 U.S.C. §§ 701-06 , (“APA”); (2) procedural due process under the Fifth Amendment; (3) equal protection under the Fourteenth Amendment; and (4) his First Amendment right to freedom of speech. In response to court-ordered discovery, the Air Force provided a list of all of the 322 medical doctors and students separated from the Air Force between the time that the Deutch Memo was written and the time this action was commenced. The list provides the reason for each service member’s discharge, whether recoupment was sought, and whether the Secretary of the Air Force found the separation voluntary. As relevant here, of the situations in which a service member made a statement of sexual orientation, the Air Force ordered recoupment in 23 out of the 28 cases. In the 277 separation cases that did not involve a coming out statement, recoupment was ordered 274 times.

On May 21, 2001, the district court reviewed the record in its entirety and granted the Air Force’s motion for summary judgment with respect to all four claims and denied Hensala’s request for further discovery on the APA and due process claims. Hensala timely appealed. We ordered the submission of this case deferred pending the United States Supreme Court’s decision in Lawrence v. Texas, — U.S.-, 123 S.Ct. 2472 , 156 L.Ed.2d 508 (2003).

We review a district court’s order granting summary judgment de novo. See Oliver v. Keller, 289 F.3d 623, 626 (9th Cir.2002). We must determine whether, when viewing the evidence in the light most favorable toward the nonmoving party, there are any genuine issues of material fact, and whether the district court correctly applied the relevant substantive law. Id. at 626 . We may not weigh evidence or determine the truth of the matter, but rather, we limit our inquiry into whether genuine issues exist for trial. See Balint v. Carson City, 180 F.3d 1047, 1050 (9th Cir.1999) (en banc). We have jurisdiction to consider this appeal pursuant to 28 U.S.C. § 1291 .

II

A

Hensala alleges that the district court erred in granting summary judgment with respect to his APA claim in light of the fact that Hensala made a clear statement of intent to serve on active duty.

Under the APA, a federal court may set aside an agency decision only if it is demonstrated to be “arbitrary, capricious, an abuse of discretion, or otherwise not in accordance with law.” 5 U.S.C. § 706 (2)(A); see Ariz. Cattle Growers’ Ass’n v. United States Fish & Wildlife, 273 F.3d 1229, 1236 (9th Cir.2001). If the evidence contained in the administrative record is susceptible to more than one *956 rational interpretation, a reviewing court may not substitute its judgment for that of the agency. See Edlund, v. Massanari, 253 F.3d 1152, 1156 (9th Cir.2001); Red-dick v. Chater, 157 F.3d 715 , 720 (9th Cir.1998).

Here, the district court did not err in concluding that substantial evidence supports both the Secretary’s initial decision to seek recoupment and the Corrections Board’s affirmance. Colonel Buraglio undertook an extensive investigation, conducted an interview, made a credibility determination, and prepared a report with his written findings. Both Colonel Buraglio and the Corrections Board relied upon these findings in concluding that Hensala informed the Air Force of his sexual orientation for the purpose of separating. Despite the existence of other reasonable interpretations of the evidence, Colonel Buraglio’s conclusion is supported by inferences drawn from the timing of Hensala’s disclosure and Colonel Buraglio’s credibility determination. Further, Colonel Buraglio and the Corrections Board’s conclusions appear to fit squarely in the language of the Deutch Memo. Because a federal court may not substitute its judgment under these circumstances, the district court properly rejected Hensala’s contention that the decision lacked an adequate factual foundation. See Edlund, 253 F.3d at 1158 (affirming an ALJ’s resolution of competing testimony in light of its provision of specific and legitimate reasons for its decision).

Hensala also advances two legal claims against the Air Force’s decision. First, Hensala argues that because the Deutch Memo provides “that the member made the statement for the purpose of seeking separation,” recoupment is proper only if a statement of sexual orientation is made with knowledge that the statement will result in separation. Hensala argues that because Colonel Buraglio did not make findings involving Hensala’s knowledge on this matter, his recommendation is incomplete, contrary to Hensala’s clear statement of intent to serve, and thus insufficient to meet the Deutch Memo standard. However, as the district court correctly noted, there is nothing in 10 U.S.C. § 2005 or the Deutch Memo that limits a finding of “purpose” to a finding of specific awareness regarding the consequences as coming out as advanced by Hensala. Thus, the district court did not err in granting summary judgment on this matter.

Second, after Lawrence was decided, Hensala alleges that the recoupment policy violates the APA because 10 U.S.C. § 2005 is “contrary to [a] constitutional right” pursuant to 5 U.S.C. § 706 (2)(B). Hensala first raised this argument after Lawrence v. Texas, - U.S. -, 123 S.Ct. 2472 , 156 L.Ed.2d 508 (2003), was decided. Because the claim has not been presented to the district court, we decline to address it on appeal. Balser v. Dep’t of Justice, 327 F.3d 903, 908 (9th Cir.2003). We do not, of course, preclude the parties from pursuing this claim on remand.

B

Hensala contends that the Air Force violated due process by presuming that any statement declaring his sexual orientation constitutes an irrebuttable finding of a service member’s intent to separate. Hensala alleges that despite a written policy providing for individualized findings, the Air Force applies its recoupment policy to all service members who make coming out statements. Hensala contends that the district court erroneously granted summary judgment on this claim and abused its discretion in denying his related discovery request because material issues of fact exist and, when viewed most favorably toward Hensala, a reason *957 able fact-finder could resolve them in his favor.

The recoupment policy on its face provides for an individualized investigation and hearing, and does not deny a service member an opportunity to present evidence as to the question of intent to separate. Cf. Vlandis v. Kline, 412 U.S. 441, 447 , 93 S.Ct. 2230 , 37 L.Ed.2d 63 (1973) (striking down policy that denied out-of-state applicants an opportunity to prove whether they were residents of Connecticut). Further, as applied to Hensala, the record demonstrates that the Air Force provided an investigation and hearing in which Hensala presented evidence that he did not come out for the purpose of separating from the Air Force.

As applied to other service members, the record demonstrates that in an approximate six year window, the Air Force ordered recoupment in 23 of the 28 cases that involved a service member who announced his or her sexual orientation. The district court analyzed the findings of these cases, as characterized by each of the parties, and concluded that the Air Force made individualized determinations with respect to each service member’s intent to separate.

Even viewing the evidence in the light most favorable toward Hensala, the record demonstrates that the Air Force orders recoupment after individualized determinations of intent and does not, in policy or in practice, circumvent the investigation by applying an irrebuttable presumption. Any further evidence relating to situations in which recoupment was ordered does not undercut the demonstrated individualized practices employed by the Air Force. Accordingly, the district court neither erred in granting summary judgment on this claim nor abused its discretion in denying further discovery or denying Hensala’s Rule 56(f) motion relating to the Air Forces’ practices towards other service members who make coming out statements. See Carlson v. Reed, 249 F.3d 876, 882 (9th Cir.2001) (holding that a university’s presumption that certain immigrants are nonresidents did not violate due process because individuals subject to the policy had an opportunity to present proof of residency); Chance v. Pac-Tel Teletrac, Inc., 242 F.3d 1151 , 1161 n. 6 (9th Cir.2001) (holding that a district court abuses its discretion in denying a Rule 56(f) motion if movant can demonstrate that additional discovery would have precluded summary judgment).

C

Hensala alleges that the Air Force violated his rights to equal protection and free speech because his status as a gay man, rather than any misconduct, triggered the recoupment policy. The district court rejected this argument, holding that Holmes v. California Army National Guard, 124 F.3d 1126 (9th Cir.1997) foreclosed consideration of these claims.

Holmes involved two service members’ constitutional challenges to 10 U.S.C. § 654 (b), the “Don’t Ask, Don’t Tell policy.” 124 F.3d at 1127 . Holmes held that the statute did not violate equal protection because the military had a legitimate interest “in discharging service members on account of homosexual conduct.” Id. at 1134 . We further concluded in Holmes that the policy was rationally related to its goal because its statutory presumption that a coming out statement indicates that the service member will not be celibate is a rebuttable presumption and that such presumption applies to “persons of homosexual and heterosexual orientation.” Id. at 1136 . Holmes also held that § 654(b) did not implicate the First Amendment because the service members’ coming out statements were evidence of misconduct, and the service members “were discharged *958 for their conduct and not for speech.” Id. at 1136. Thus, the statute was upheld as not violating equal protection or free speech because it targeted criminalized conduct and was applicable against both gay and non-gay service members.

Here, Hensala alleges that the recoupment policy targets status because a statement identifying sexual orientation is sufficient to trigger the policy. Indeed, the “Don’t Ask, Don’t Tell” policy requires an investigation into whether a service member has had sex with someone of the same gender, see § 654(b)(1). If the service member makes a coming out statement, an inquiry is required as to whether the service member can rebut with evidence of celibacy a presumption that he or she will violate § 925. See § 654(b)(2). In contrast, in the recoupment context, the Deutch Memo expressly provides that not all service members who are separated pursuant to § 654(b)(1), are candidates for recoupment. The Deutch Memo enumerates the basis under which a coming out statement will trigger an investigation:

The Deutch Memo does not account for the fact that the “Don’t Ask, Don’t Tell” policy also is applied against heterosexual service members who violate § 925. If it is demonstrated that the recoupment policy only targets individuals who identify themselves as gay, the recoupment policy is treating similarly-situated individuals, those who violate § 925 and are discharged based on § 654(b)(1), differently based on their sexual orientation status alone. Unlike the “Don’t Ask, Don’t Tell” policy that applies against service members of all sexual orientations who engage in sexual acts with someone of the same gender, see § 654(b)(1), the record demonstrates that there are genuine issues of material fact as to whether the recoupment policy applies exclusively to service members who are gay and not simply to all service members who violate § 925.

Moreover, unlike the “Don’t Ask, Don’t Tell” policy, there is no presumption under the recoupment policy, that a coming out statement presents a rebuttable presumption that the service member has violated § 925. The statement thus is not admissible evidence of conduct, but rather, presents a genuine issue of material fact that the armed forces impermissibly is directing its policies against a service member based on his sexual orientation. If it is demonstrated that the armed forces is discriminating based on status, Hensala’s equal protection and first amendment claims present genuine issues that need to be resolved at trial. See, e.g., Limón v. Kansas, — U.S.-, 123 S.Ct. 2638 , 156 L.Ed.2d 652 (2003) (vacating and remanding equal protection challenge brought by gay man claiming criminal statute provided unequal treatment on the basis of sexual orientation “to the Court of Appeals of Kansas for further consideration in light of Lawrence v. Texas ”).

Because Holmes limits its inquiry into the armed forces’ separation policy that is predicated on a finding of impermissible conduct, Holmes does not foreclose a claim that the separate recoupment policy ap *959 plies only to service members based on their status. See, e.g., Watson v. United States, 49 Fed. Cl. 728, 731-32 (2001) (holding that the legal analysis set forth in Holmes does not foreclose a challenge to the armed forces’ separation pay policy as applied to a discharged service member). The district court erred thus as a matter of law. We need not, and do not, reach the question of whether Lawrence v. Texas, — U.S. -, 123 S.Ct. 2472 , 156 L.Ed.2d 508 (2003) has effectively overruled Holmes .

Ill

We affirm the district court’s grant of summary judgment on Hensala’s APA, Due Process, and Rule 56(f) claims. We reverse the district court’s grant of summary judgment on his Equal Protection and First Amendment claims and remand for further proceedings.

Each party to bear its own costs.

AFFIRMED IN PART; REVERSED IN PART; REMANDED.